package com.leetcode.design;

class MyCircularQueue {

    public static void main(String[] args) {
        MyCircularQueue obj = new MyCircularQueue(3);
        obj.enQueue(1);
        obj.enQueue(2);
        obj.enQueue(3);
        obj.enQueue(4);
        int rear = obj.Rear();
        boolean full = obj.isFull();
        boolean b = obj.deQueue();
        obj.enQueue(4);
        int rear2 = obj.Rear();
    }

    static class Node {
        int value;
        Node prev, next;

        public Node(int value) {
            this.value = value;
        }
    }

    private int size, k;

    private Node head, rear;

    /**
     * Initialize your data structure here. Set the size of the queue to be k.
     */
    public MyCircularQueue(int k) {
        this.k = k;
        head = new Node(-1);
        rear = new Node(-1);
        head.next = rear;
        head.prev = rear;
        rear.prev = head;
        rear.next = head;
    }

    /**
     * Insert an element into the circular queue. Return true if the operation is successful.
     */
    public boolean enQueue(int value) {
        if (size == k) return false;
        Node node = new Node(value);
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        node.prev = head;
        size++;
        return true;
    }

    /**
     * Delete an element from the circular queue. Return true if the operation is successful.
     */
    public boolean deQueue() {
        if (size == 0) return false;
        Node node = rear.prev.prev;
        node.next = rear;
        rear.prev = node;
        size--;
        return true;
    }

    /**
     * Get the front item from the queue.
     */
    public int Front() {
        return size == 0 ? -1 : rear.prev.value;
    }

    /**
     * Get the last item from the queue.
     */
    public int Rear() {
        return size == 0 ? -1 : head.next.value;
    }

    /**
     * Checks whether the circular queue is empty or not.
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Checks whether the circular queue is full or not.
     */
    public boolean isFull() {
        return size == k;
    }
}
